<!DOCTYPE html>
<html>
<head>
	<title>Canvas Demo</title>
	    <style>
      #myCanvas {
        border: 1px solid #000;
      }
    </style>
</head>
<body>
需要先了解多边形排样算法的基本原理。多边形排样也被称为矩形排样，是指将多个不规则形状的矩形或者多边形按照一定的规则排列在一个矩形或者一个有限空间内，使得它们的面积利用率达到最大。

以下是一个简单的多边形排样算法：

1. 找到面积最大的多边形并将其放置在左下角，将其边缘与容器边缘对齐；

2. 将剩余的多边形按照面积递减的顺序依次放入容器内；

3. 对于每个多边形，尝试将其放置在容器内的所有可能位置，找到一个空间利用率最大的位置。

如果多边形之间的距离为零，则会出现重叠的情况。这时可以采用以下方法：

1. 找到两个重叠的多边形；

2. 针对每个多边形，找到一个可以移动的位置，使得两个多边形不再重叠；

3. 重新计算容器内所有多边形的位置，直到不存在重叠的多边形。

如果某个多边形超出容器范围，则可以采用以下方法：

1. 判断多边形是否有部分在容器外面；

2. 如果是，找到一个可以移动的位置使得多边形完全在容器内；

3. 重新计算容器内所有多边形的位置，直到不存在多边形超出容器范围。
	<canvas id="myCanvas"></canvas>
	<script>
	
function polyPack(polygons, width, height) {
  // 计算多边形面积和排序
  polygons = polygons.map((poly) => ({
    area: calcArea(poly),
    poly,
  })).sort((a, b) => b.area - a.area);
  const container = {
    x: 0,
    y: 0,
    width,
    height,
    polys: [polygons[0].poly],
  };
  const count = polygons.length - 1;
  for (let i = 0; i < count; i++) {
    const poly = polygons[i + 1].poly;
    let bestNode = null;
    let bestX, bestY;
    for (let j = 0; j < container.polys.length; j++) {
      const node = fitPolyInPolygon(poly, container.polys[j]);
      if (node) {
        if (!bestNode || node.utilization > bestNode.utilization) {
          bestNode = node;
          bestX = node.x;
          bestY = node.y;
        }
      }
    }
    if (!bestNode) {
      // 无法放置，扩大容器
      container.x = container.y = 0;
      container.width *= 2;
      container.height *= 2;
      i--;
    } else {
      poly.x = bestX;
      poly.y = bestY;
      container.polys.push(poly);
    }
  }
  return container.polys;
}
// 计算多边形面积
function calcArea(poly) {
  let area = 0;
  for (let i = 0; i < poly.length; i++) {
    const j = (i + 1) % poly.length;
    area += poly[i].x * poly[j].y - poly[j].x * poly[i].y;
  }
  return area / 2;
}
// 判断多边形是否在容器内部
function isPolyInPolygon(poly, container) {
  for (let i = 0; i < poly.length; i++) {
    const pt = poly[i];
    if (!isPtInPolygon(pt, container)) {
      return false;
    }
  }
  return true;
}
// 判断点是否在多边形内部
function isPtInPolygon(pt, poly) {
  let isInside = false;
  for (let i = 0, j = poly.length - 1; i < poly.length; j = i++) {
    const intersect =
      poly[i].y > pt.y !== poly[j].y > pt.y &&
      pt.x < ((poly[j].x - poly[i].x) * (pt.y - poly[i].y)) /
        (poly[j].y - poly[i].y) +
        poly[i].x;
    if (intersect) {
      isInside = !isInside;
    }
  }
  return isInside;
}
// 计算两个多边形的最小覆盖矩形，并返回适合放置新多边形的可行区域
function fitPolyInPolygon(poly, container) {
  const maxBox = calcMaxBox(poly, container);
  if (!maxBox) {
    return null;
  }
  const nodes = [
    {
      x: maxBox.x,
      y: maxBox.y,
      utilization: calcUtilization(poly, {
        x: maxBox.x,
        y: maxBox.y,
        width: maxBox.width,
        height: maxBox.height,
      }),
    },
    {
      x: maxBox.x + maxBox.width,
      y: maxBox.y,
      utilization:calcUtilization(poly, {
        x: maxBox.x + maxBox.width,
        y: maxBox.y,
        width: maxBox.width,
        height: maxBox.height,
      }),
    },
    {
      x: maxBox.x + maxBox.width,
      y: maxBox.y + maxBox.height,
      utilization: calcUtilization(poly, {
        x: maxBox.x + maxBox.width,
        y: maxBox.y + maxBox.height,
        width: maxBox.width,
        height: maxBox.height,
      }),
    },
    {
      x: maxBox.x,
      y: maxBox.y + maxBox.height,
      utilization: calcUtilization(poly, {
        x: maxBox.x,
        y: maxBox.y + maxBox.height,
        width: maxBox.width,
        height: maxBox.height,
      }),
    },
  ];
  let bestNode = null;
  for (let i = 0; i < nodes.length; i++) {
    const node = nodes[i];
    if (isPolyInPolygon(poly, { ...container, x: node.x, y: node.y })) {
      if (!bestNode || node.utilization > bestNode.utilization) {
        bestNode = node;
      }
    }
  }
  return bestNode;
}
// 计算多边形最小覆盖矩形
function calcMaxBox(poly, container) {
  let xMin = Infinity,
    yMin = Infinity,
    xMax = -Infinity,
    yMax = -Infinity;
  for (let i = 0; i < poly.length; i++) {
    xMin = Math.min(xMin, poly[i].x);
    yMin = Math.min(yMin, poly[i].y);
    xMax = Math.max(xMax, poly[i].x);
    yMax = Math.max(yMax, poly[i].y);
  }
  if (
    xMax - xMin > container.width ||
    yMax - yMin > container.height ||
    xMin < container.x ||
    xMax > container.x + container.width ||
    yMin < container.y ||
    yMax > container.y + container.height
  ) {
    return null;
  }
  return {
    x: xMin,
    y: yMin,
    width: xMax - xMin,
    height: yMax - yMin,
  };
}
// 计算多边形与矩形的面积利用率
function calcUtilization(poly, box) {
  // 计算多边形与矩形的重叠区域面积
  let overlapArea = 0;
  for (let i = 0; i < poly.length; i++) {
    const j = (i + 1) % poly.length;
    const intersect = findLineIntersection(
      poly[i],
      poly[j],
      { x: box.x, y: box.y },
      { x: box.x + box.width, y: box.y }
    ) ||
      findLineIntersection(
        poly[i],
        poly[j],
        { x: box.x + box.width, y: box.y },
        { x: box.x + box.width, y: box.y + box.height }
      ) ||
      findLineIntersection(
        poly[i],
        poly[j],
        { x: box.x + box.width, y: box.y + box.height },
        { x: box.x, y: box.y + box.height }
      ) ||
      findLineIntersection(
        poly[i],
        poly[j],
        { x: box.x, y: box.y + box.height },
        { x: box.x, y: box.y }
      );
    if (intersect) {
      const a = dist(poly[i], intersect);
      const b = dist(poly[j], intersect);
      overlapArea += (a + b) / 2;
    }
  }
  return overlapArea / (box.width * box.height);
}
// 计算两条直线之间的交点
function findLineIntersection(p1, p2, p3, p4) {
  const ua =
    ((p4.x - p3.x) * (p1.y - p3.y) - (p4.y - p3.y) * (p1.x - p3.x)) /
    ((p4.y - p3.y) * (p2.x - p1.x) - (p4.x - p3.x) * (p2.y - p1.y));
  const x = p1.x + ua * (p2.x - p1.x);
  const y = p1.y + ua * (p2.y - p1.y);
  if (
    x < Math.min(p1.x, p2.x) ||
    x > Math.max(p1.x, p2.x) ||
    x < Math.min(p3.x, p4.x) ||
    x > Math.max(p3.x, p4.x)
  ) {
    return null;
  }
  if (
    y < Math.min(p1.y, p2.y) ||
    y > Math.max(p1.y, p2.y) ||
    y < Math.min(p3.y, p4.y) ||
    y > Math.max(p3.y, p4.y)
  ) {
    return null;
  }
  return { x, y };
}
// 计算两个点之间的距离
function dist(p1, p2) {
  const dx = p2.x - p1.x;
  const dy = p2.y - p1.y;
  return Math.sqrt(dx * dx + dy * dy);
}
	
	
	
		let canvas = document.getElementById("myCanvas");
		let ctx = canvas.getContext("2d");
		canvas.width = 400;
		canvas.height = 800;
        let jsonData =   [
    {
      "nodeX": 0,
      "nodeY": 0,
      "length": 214,
      "width": 31,
      "nodeEndX": 214,
      "nodeEndY": 31,
      "isOrder": true,
      "area": 6634
    },
    {
      "nodeX": 0,
      "nodeY": 31,
      "length": 58,
      "width": 24,
      "nodeEndX": 58,
      "nodeEndY": 55,
      "isOrder": true,
      "area": 1392
    },
    {
      "nodeX": 0,
      "nodeY": 55,
      "length": 219,
      "width": 57,
      "nodeEndX": 219,
      "nodeEndY": 112,
      "isOrder": true,
      "area": 12483
    },
    {
      "nodeX": 0,
      "nodeY": 112,
      "length": 91,
      "width": 21,
      "nodeEndX": 91,
      "nodeEndY": 133,
      "isOrder": true,
      "area": 1911
    },
    {
      "nodeX": 0,
      "nodeY": 133,
      "length": 99,
      "width": 100,
      "nodeEndX": 99,
      "nodeEndY": 233,
      "isOrder": true,
      "area": 9900
    },
    {
      "nodeX": 0,
      "nodeY": 233,
      "length": 134,
      "width": 71,
      "nodeEndX": 134,
      "nodeEndY": 304,
      "isOrder": true,
      "area": 9514
    },
    {
      "nodeX": 0,
      "nodeY": 304,
      "length": 97,
      "width": 69,
      "nodeEndX": 97,
      "nodeEndY": 373,
      "isOrder": true,
      "area": 6693
    },
    {
      "nodeX": 97,
      "nodeY": 304,
      "length": 179,
      "width": 75,
      "nodeEndX": 276,
      "nodeEndY": 379,
      "isOrder": true,
      "area": 13425
    },
    {
      "nodeX": 58,
      "nodeY": 31,
      "length": 143,
      "width": 24,
      "nodeEndX": 201,
      "nodeEndY": 55,
      "isOrder": true,
      "area": 3432
    },
    {
      "nodeX": 99,
      "nodeY": 112,
      "length": 156,
      "width": 119,
      "nodeEndX": 255,
      "nodeEndY": 231,
      "isOrder": true,
      "area": 18564
    },
    {
      "nodeX": 219,
      "nodeY": 0,
      "length": 113,
      "width": 90,
      "nodeEndX": 332,
      "nodeEndY": 90,
      "isOrder": true,
      "area": 10170
    },
    {
      "nodeX": 255,
      "nodeY": 90,
      "length": 78,
      "width": 77,
      "nodeEndX": 333,
      "nodeEndY": 167,
      "isOrder": true,
      "area": 6006
    },
    {
      "nodeX": 134,
      "nodeY": 231,
      "length": 159,
      "width": 30,
      "nodeEndX": 293,
      "nodeEndY": 261,
      "isOrder": true,
      "area": 4770
    },
    {
      "nodeX": 276,
      "nodeY": 261,
      "length": 77,
      "width": 105,
      "nodeEndX": 353,
      "nodeEndY": 366,
      "isOrder": true,
      "area": 8085
    },
    {
      "nodeX": 255,
      "nodeY": 167,
      "length": 179,
      "width": 61,
      "nodeEndX": 434,
      "nodeEndY": 228,
      "isOrder": true,
      "area": 10919
    },
    {
      "nodeX": 333,
      "nodeY": 0,
      "length": 152,
      "width": 101,
      "nodeEndX": 485,
      "nodeEndY": 101,
      "isOrder": true,
      "area": 15352
    },
    {
      "nodeX": 353,
      "nodeY": 228,
      "length": 142,
      "width": 103,
      "nodeEndX": 495,
      "nodeEndY": 331,
      "isOrder": true,
      "area": 14626
    },
    {
      "nodeX": 434,
      "nodeY": 101,
      "length": 113,
      "width": 113,
      "nodeEndX": 547,
      "nodeEndY": 214,
      "isOrder": true,
      "area": 12769
    },
    {
      "nodeX": 495,
      "nodeY": 214,
      "length": 70,
      "width": 109,
      "nodeEndX": 565,
      "nodeEndY": 323,
      "isOrder": true,
      "area": 7630
    },
    {
      "nodeX": 0,
      "nodeY": 373,
      "length": 50,
      "width": 23,
      "nodeEndX": 50,
      "nodeEndY": 396,
      "isOrder": true,
      "area": 1150
    },
    {
      "nodeX": 547,
      "nodeY": 0,
      "length": 114,
      "width": 118,
      "nodeEndX": 661,
      "nodeEndY": 118,
      "isOrder": true,
      "area": 13452
    },
    {
      "nodeX": 50,
      "nodeY": 379,
      "length": 215,
      "width": 21,
      "nodeEndX": 265,
      "nodeEndY": 400,
      "isOrder": true,
      "area": 4515
    },
    {
      "nodeX": 547,
      "nodeY": 118,
      "length": 116,
      "width": 93,
      "nodeEndX": 663,
      "nodeEndY": 211,
      "isOrder": true,
      "area": 10788
    },
    {
      "nodeX": 565,
      "nodeY": 211,
      "length": 107,
      "width": 84,
      "nodeEndX": 672,
      "nodeEndY": 295,
      "isOrder": true,
      "area": 8988
    },
    {
      "nodeX": 353,
      "nodeY": 331,
      "length": 156,
      "width": 67,
      "nodeEndX": 509,
      "nodeEndY": 398,
      "isOrder": true,
      "area": 10452
    },
    {
      "nodeX": 565,
      "nodeY": 295,
      "length": 78,
      "width": 79,
      "nodeEndX": 643,
      "nodeEndY": 374,
      "isOrder": true,
      "area": 6162
    },
    {
      "nodeX": 643,
      "nodeY": 295,
      "length": 119,
      "width": 51,
      "nodeEndX": 762,
      "nodeEndY": 346,
      "isOrder": true,
      "area": 6069
    },
    {
      "nodeX": 661,
      "nodeY": 0,
      "length": 130,
      "width": 57,
      "nodeEndX": 791,
      "nodeEndY": 57,
      "isOrder": true,
      "area": 7410
    },
    {
      "nodeX": 333,
      "nodeY": 101,
      "length": 91,
      "width": 49,
      "nodeEndX": 424,
      "nodeEndY": 150,
      "isOrder": true,
      "area": 4459
    },
    {
      "nodeX": 134,
      "nodeY": 261,
      "length": 79,
      "width": 41,
      "nodeEndX": 213,
      "nodeEndY": 302,
      "isOrder": true,
      "area": 3239
    },
    {
      "nodeX": 663,
      "nodeY": 57,
      "length": 121,
      "width": 117,
      "nodeEndX": 784,
      "nodeEndY": 174,
      "isOrder": true,
      "area": 14157
    },
    {
      "nodeX": 643,
      "nodeY": 346,
      "length": 109,
      "width": 42,
      "nodeEndX": 752,
      "nodeEndY": 388,
      "isOrder": true,
      "area": 4578
    },
    {
      "nodeX": 672,
      "nodeY": 174,
      "length": 94,
      "width": 46,
      "nodeEndX": 766,
      "nodeEndY": 220,
      "isOrder": true,
      "area": 4324
    },
    {
      "nodeX": 485,
      "nodeY": 0,
      "length": 55,
      "width": 85,
      "nodeEndX": 540,
      "nodeEndY": 85,
      "isOrder": true,
      "area": 4675
    }
  ];
        jsonData.forEach(function(data) {
          /*
		    ctx.lineWidth = 2;
		    ctx.strokeStyle =randomColor();
			
		    ctx.stroke(); 
            ctx.strokeRect(data.nodeX, data.nodeY, data.length, data.width);
			
			*/
			
			ctx.fillStyle = randomColor();
			ctx.fillRect(data.nodeX, data.nodeY, data.length, data.width);
        });
		
		
		function randomColor() {
		   var color = "#";
		   for (var i = 0; i < 6; i++) color+=parseInt(Math.random() * 16).toString(16);		   
		   console.log(color);
		   return color;
		}
	</script>
</body>
</html>